/*
 * 合并二叉树， 比较经典的dfs和bfs题目， 理解两种搜索
 * */

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:

    //bfs的写法
    TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2) {
        if (t1 == nullptr) {
            return t2;
        }
        if (t2 == nullptr) {
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        auto q = queue<TreeNode *>();
        q.push(merged);
        auto q1 = queue<TreeNode *>();
        auto q2 = queue<TreeNode *>();
        q1.push(t1);
        q2.push(t2);

        while (!q1.empty() || !q2.empty()) {
            auto node = q.front(), left1 = q1.front()->left,
                    left2 = q2.front()->left, right1 = q1.front()->right,
                    right2 = q2.front()->right;

            q.pop();
            q1.pop();
            q2.pop();
            if (left1 != nullptr && left2 != nullptr) {
                auto left = new TreeNode(left1->val + left2->val);
                node->left = left;
                q.push(left);
                q1.push(left1);
                q2.push(left2);
            } else if (left1 != nullptr) {
                node->left = left1;
            } else if (left2 != nullptr) {
                node->left = left2;
            }

            if (right1 != nullptr && right2 != nullptr) {
                auto right = new TreeNode(right1->val + right2->val);
                node->right = right;
                q.push(right);
                q1.push(right1);
                q2.push(right2);
            } else if (right1 != nullptr) {
                node->right = right1;
            } else if (right2 != nullptr) {
                node->right = right2;
            }
        }
        return merged;
    }

    TreeNode* mergeTrees2(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr) {
            return t2;
        }
        if (t2 == nullptr) {
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};

void printTree(TreeNode *node) {
    if (!node) {
        return;
    }
    queue<TreeNode *> stk;
    stk.push(node);
    while (!stk.empty()) {
        auto prev = stk.front();
        cout << prev->val << " ";
        auto left = prev->left;
        auto right = prev->right;
        stk.pop();
        if (left != nullptr) {
            stk.push(left);
        }
        if (right != nullptr) {
            stk.push(right);
        }
    }
}

int main() {
    auto node1 = new TreeNode(1);
    node1->left = new TreeNode(3);
    node1->right = new TreeNode(2);
    node1->left->left = new TreeNode(5);

    auto node2 = new TreeNode(2);
    node2->left = new TreeNode(1);
    node2->right = new TreeNode(3);
    node2->left->right = new TreeNode(4);
    node2->right->right = new TreeNode(7);

    Solution solution;
    auto res = solution.mergeTrees(node1, node2);
    printTree(res);

    return 0;
}